Verify preorder serialization of a binary tree

Time: O(N); Space: O(1); medium

One way to serialize a binary tree is to use pre-oder traversal.

When we encounter a non-null node, we record the node’s value.

If it is a null node, we record using a sentinel value such as #.

        _9_
     /       \
    3         2
  /  \       / \
 4    1     #   6
/ \  / \       / \
#  ##   #     #   #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1:

Input: “9,3,4,#,#,1,#,#,2,#,6,#,#”

Output: True

Example 2:

Input: “1,#”

Return False

Example 3:

Input: “9,#,#,1”

Output: False

[1]:

class Solution1(object):
    def isValidSerialization(self, preorder: str) -> bool:
        """
        :type preorder: str
        :rtype: bool
        """
        def split_iter(s, tok):
            start = 0
            for i in range(len(s)):
                if s[i] == tok:
                    yield s[start:i]
                    start = i + 1
            yield s[start:]

        if not preorder:
            return False

        depth, cnt = 0, preorder.count(',') + 1
        for tok in split_iter(preorder, ','):
            cnt -= 1
            if tok == "#":
                depth -= 1;
                if depth < 0:
                    break
            else:
                depth += 1
        return cnt == 0 and depth < 0

[2]:

s = Solution1()
preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
assert s.isValidSerialization(preorder) == True
preorder = "1,#"
assert s.isValidSerialization(preorder) == False
preorder = "9,#,#,1"
assert s.isValidSerialization(preorder) == False